package leetcode101.linked_list;

/**
 * @author Synhard
 * @version 1.0
 * @class Code9
 * @description 148. 排序链表
 * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 *
 * 进阶：
 *
 * 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-06-12 20:45
 */
public class Code9 {

    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        System.out.println(sortList(head));
    }

    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 创建尾结点
        ListNode rear = head;
        while (rear.next != null) {
            rear = rear.next;
        }
        return mergeSort(head, rear);
    }

    private static ListNode mergeSort(ListNode left, ListNode right) {
        if (left == right) {
            return left;
        }
        ListNode mid = getMedium(left, right);
        ListNode leftSorted = mergeSort(left, mid);
        ListNode rightSorted = mergeSort(mid.next, right);
        // 下面这一步尤为重要
        mid.next = null;
        return merge(leftSorted, rightSorted);
    }

    private static ListNode getMedium(ListNode left, ListNode right) {
        if (left == null || right == null) {
            return left == null ? right : left;
        }
        ListNode dummyHead = new ListNode(-1, left);
        ListNode slow = dummyHead, fast = dummyHead;
        while (fast != right && fast != right.next) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private static ListNode merge(ListNode head1, ListNode head2) {
        if (head1 == null || head2 == null) {
            return head1 == null ? head2 : head1;
        }
        ListNode newHead;
        if (head1.val <= head2.val) {
            newHead = merge(head1.next, head2);
            head1.next = newHead;
            return head1;
        } else {
            newHead = merge(head2.next, head1);
            head2.next = newHead;
            return head2;
        }
    }

}

/*
这道题对链表基本操作以及归并排序思想进行考察
大致思路就是对链表进行拆分然后进行归并排序
首先需要根据链表的头节点找到链表的中点以及末尾，这一步考察了返回链表的倒数第k个结点/返回链表中点
然后对链表的左半部分进行排序，右半部分进行排序
将两部分排序好的链表进行合并，这一步考察了将两个有序链表的递归合并
其中对排序好的两个链表在归并之前要把中点的next设置为空！
 */